﻿#region Copyright (c) 2003 - 2008, Andreas Mueller
/////////////////////////////////////////////////////////////////////////////////////////
// 
// Copyright (c) 2003 - 2008, Andreas Mueller.
// All rights reserved. This program and the accompanying materials
// are made available under the terms of the Eclipse Public License v1.0
// which accompanies this distribution, and is available at
// http://www.eclipse.org/legal/epl-v10.html
//
// Contributors:
//    Andreas Mueller - initial API and implementation
//
// 
// This software is derived from software bearing the following
// restrictions:
// 
// Copyright (c) 1994
// Hewlett-Packard Company
// 
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Hewlett-Packard Company makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
// 
// 
// Copyright (c) 1996,1997
// Silicon Graphics Computer Systems, Inc.
// 
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Silicon Graphics makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
// 
// 
// (C) Copyright Nicolai M. Josuttis 1999.
// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all copies.
// This software is provided "as is" without express or implied
// warranty, and with no claim as to its suitability for any purpose.
// 
/////////////////////////////////////////////////////////////////////////////////////////
#endregion


using System.Collections;
using NStl.Collections;
using NStl.NUnit.AlgorithmFixtures.Heap;
using NUnit.Framework;
using NStl.SyntaxHelper;

namespace NStl.NUnit.AlgorithmFixtures.Heap
{
    [TestFixture]
    public class PushHeapWithPredicateFixture : AbstractPushHeapFixture
    {
        // ... A heap is a particular way of ordering the elements in a range of random 
        // ... access iterators [f, l). The reason heaps are useful (especially for sorting, 
        // ... or as priority queues) is that they satisfy two important properties. 
        // ... First, *f is the largest element in the heap. Second, it is possible to 
        // ... add an element to a heap (using push_heap), or to remove *f, in logarithmic 
        // ... time. Internally, a heap is a tree represented as a sequential range. The tree 
        // ... is constructed so that that each node is less than or equal to its parent node.
        [Test]
        public override void SuccessfullPass()
        {
            Assert.AreEqual(1, heap.Front());
            heap.PushBack(0);
            Algorithm.PushHeap(heap.Begin(), heap.End(), Compare.Greater<int>());
            Assert.AreEqual(0, heap.Front());
            Assert.AreEqual(1, heap[1]);
        }
        [SetUp]
        public override void SetUp()
        {
            base.SetUp();
            Algorithm.MakeHeap(heap.Begin(), heap.End(), Compare.Greater<int>());
        }


        [Test]
        public override void NonSuccessfullPass()
        {
            Assert.AreEqual(1, heap.Front());
            heap.PushBack(42);
            Algorithm.PushHeap(heap.Begin(), heap.End(), Compare.Greater<int>());
            Assert.AreEqual(1, heap.Front());
        }

        [Test]
        public override void StartIteratorIsEqualToEndIterator()
        {
            ICollection expected = new Vector<int>(heap);
            Algorithm.PushHeap(heap.Begin(), heap.Begin(), Compare.Greater<int>());
            CollectionAssert.AreEqual(expected, heap);
        }
    }
}
